/*
 * @lc app=leetcode.cn id=42 lang=golang
 *
 * [42] 接雨水
 */

// @lc code=start
// todo 使用动态规划重写
func trap(height []int) int {
	n := len(height)
	left, right := 0, n-1
	leftmax, rightmax := 0, 0
	sum := 0
	for left < right {
		if height[left] > leftmax {
			leftmax = height[left]
		}
		if height[right] > rightmax {
			rightmax = height[right]
		}
		if height[left] < height[right] {
			sum += leftmax - height[left]
			left++
		} else {
			sum += rightmax - height[right]
			right--
		}
	}
	return sum
}

// @lc code=end
